package medium;

import java.util.*;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2021/7/22 19:58
 */
public class No15_三数之和 {
    public static void main(String[] args) {
        Solution15 solution15 = new Solution15();
        int[] nums = new int[]{2, 2, 3, -4, 7, -9};
        List<List<Integer>> lists = solution15.threeSum(nums);
        System.out.println();
    }
}


class Solution15 {
    public List<List<Integer>> threeSum(int[] nums) {
        //排序
        Arrays.sort(nums);
        //长度
        int length = nums.length;
        List<List<Integer>> res = new ArrayList<>();
        for (int big = 0; big < length; big++) {
            //1.处理big跳过问题,考虑0的情况,和>0(big位置)情况
            if (big > 0 && nums[big] == nums[big - 1]) {
                //优化
                continue;
            }
            int red = big + 1;
            int green = length - 1;
            while (red < green) {
                if (red > big + 1 && nums[red] == nums[red - 1]) {
                    red++;
                    continue;
                }
                if (green < length - 1 && nums[green] == nums[green + 1]) {
                    green--;
                    continue;
                }
                
                //经过上面处理,指向的值一定不重复
                int a = nums[red];
                int b = nums[green];
                int c = nums[big];
                //详细展示
                int check = c;
                int target = -check;
                if (a + b > target) {
                    green--;
                } else if (a + b < target) {
                    red++;
                } else {
                    List<Integer> list = new ArrayList<>();
                    list.add(a);
                    list.add(b);
                    list.add(c);
                    res.add(list);
                    //指针移动,否则死循环!!!!
                    red++;
                    green--;
                }
            }
        }
        return res;
    }
}



    //public List<List<Integer>> threeSum(int[] nums) {
    //    //暴力法优化:排序
    //    Arrays.sort(nums);
    //    int length = nums.length;
    //    //存放元素
    //    int[] yuansus = new int[3];
    //    //元素拼接用于去重
    //    Set<String> set = new HashSet<>();
    //    List<List<Integer>> res = new ArrayList<>();
    //    for (int big = 0; big < length; big++) {
    //        int red =  0;
    //        int green = length - 1;
    //        //发现问题,red跟big相同或者green跟big相同->bug!!!
    //        while (red<green) {
    //            if (red == big) {
    //                red++;
    //                continue;
    //            }
    //            if (green == big) {
    //                green--;
    //                continue;
    //            }
    //            //可以处理
    //            int a = nums[red];
    //            int b = nums[green];
    //            int c = nums[big];
    //            //清晰展示
    //            int check = nums[big];
    //            //a+b的目标值
    //            int target = -check;
    //            //通过目标值与a+b的大小移动红绿指针
    //            if (a + b > target) {
    //                green--;
    //            } else if (a + b < target) {
    //                red++;
    //            } else {
    //                //相同,说明a+b+c = 0,数锯扔入!!
    //                //-4,2,2跟 2,-4,2类似这种如何处理
    //                yuansus[0] = a; // 2
    //                yuansus[1] = b; // -4
    //                yuansus[2] = c; // 2
    //                //排序,去重,一定要排序
    //                Arrays.sort(yuansus);
    //                String base = yuansus[0] + "_" + yuansus[1] + "_" + yuansus[2];
    //                if (set.add(base)) {
    //                    //效率提升
    //                    List<Integer> list = new ArrayList<>();
    //                    //-4,2,2
    //                    list.add(yuansus[0]);
    //                    list.add(yuansus[1]);
    //                    list.add(yuansus[2]);
    //                    res.add(list);
    //                }
    //                
    //                //指针移动,否则死循环!!!!
    //                red++;
    //                green--;
    //                
    //            } 
    //            
    //        }
    //    }
    //    return res;
    //}



    //public List<List<Integer>> threeSum(int[] nums) {
    //    //2, 2, 3, -4, 7, -9-> [2,2,-4] [2,7,-9] [应该没有了????]
    //    //1.所有 2.不重复
    //    //暴力法,啥都想不出来,先用这个方法试试水!!!
    //    int length = nums.length;
    //
    //    //用于存放摘取的元素排序用
    //    int[] yuansus = new int[3];
    //    //放形如-4_2_2这样的字符串,用于去重
    //    Set<String> set = new HashSet<>();
    //    for (int i = 0; i < length; i++) {
    //        for (int j = 0; j < length; j++) {
    //            for (int k = 0; k < length; k++) {
    //                //均不重复,故:
    //                if (i != j && j != k && i != k && (nums[i] + nums[j] + nums[k] == 0)) {
    //                    //i!=j!=k
    //                    //获取元素
    //                    int a = nums[i];
    //                    int b = nums[j];
    //                    int c = nums[k];
    //
    //                    //有什么问题?
    //                    //问题:2,2,-4 跟 -4,2,2如何判断是同一个???
    //                    //放数组,排序,拼字符串
    //                    //-4,2,2  -4,2,2 扔set去重!!!
    //                    //十分麻烦!!
    //                    yuansus[0] = a;
    //                    yuansus[1] = b;
    //                    yuansus[2] = c;
    //                    //排序,用于去重
    //                    Arrays.sort(yuansus);
    //                    //-4_2_2
    //                    String base = yuansus[0] + "_" + yuansus[1] + "_" + yuansus[2];
    //                    set.add(base);
    //                }
    //            }
    //        }
    //    }
    //    
    //    //List<List<Integer>>
    //    List<List<Integer>> res = new ArrayList<>();
    //    
    //    //遍历set,出结果
    //    //比如:nums:2, 2, 3, -4, 7, -9 
    //    for (String s : set) {
    //        //s:-4_2_2, -9_2_7
    //        List<Integer> list = new ArrayList<>();
    //        list.add(Integer.valueOf(s.split("_")[0]));
    //        list.add(Integer.valueOf(s.split("_")[1]));
    //        list.add(Integer.valueOf(s.split("_")[2]));
    //        res.add(list);
    //    }
    //    System.out.println();
    //    return res;
    //}





